package leetcode_周赛._2022._202201._09;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/1/9 22:32
 * 统计追加字母可以获得的单词数
 * 算法：位运算
 */
public class _5978 {

    public int wordCount(String[] startWords, String[] targetWords) {
        Map<Integer, Integer> map = new HashMap<>(targetWords.length);
        for (String s : targetWords) {
            int num = code(s);
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int ans = 0;
        for (String s : startWords) {
            int num = code(s);
            for (int i = 0; i < 26; i++) {
                // search 表示 num 加上这一个字母后，在 target 中是否存在
                int letter = 1 << i, search = num | letter;
                // num & letter = 0, 表示在 s 中也没有这个字母
                if ((num & letter) == 0 && map.containsKey(search)) {
                    ans += map.get(search);
                    map.remove(search);
                }
            }
        }
        return ans;
    }
    int code(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) res |= 1 << (s.charAt(i) - 'a');
        return res;
    }

}
